package leetcode;
/*
* 最小路径和
* */
public class Day13 {
    public int minPathSum(int[][] grid) {
    int m=grid.length;
    int n=grid[0].length;
    int[][] dp=new int[m+1][n+1];
    for (int i=0;i<=m;i++){
        dp[i][0]= Integer.MAX_VALUE;
    }
    for (int i=0;i<=n;i++){
        dp[0][i]=Integer.MAX_VALUE;
    }
    dp[0][1]=0;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
        }
    }
    return dp[m][n];
    }
    public int calculateMinimumHP1(int[][] dungeon) {
    int m=dungeon.length;
    int n=dungeon[0].length;
    int[][] dp=new int[m+1][n+1];
    for (int i=0;i<=m;i++){
            dp[i][0]= Integer.MAX_VALUE;
        }
        for (int i=0;i<=n;i++){
            dp[0][i]=Integer.MAX_VALUE;
        }
        dp[0][1]=0;
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                int min=Math.min(dp[i-1][j],dp[i][j-1]);
                if(dungeon[i-1][j-1]>=min){
                    dp[i][j]=min;
                }else {
                    dp[i][j]=min-dungeon[i-1][j-1];
                }
            }
        }
        return dp[m][n]+1;
    }
    /*
    * 地下城游戏
    * */
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        for (int i=0;i<=n;i++){
            dp[m][i]=Integer.MAX_VALUE;
        }
        for (int i=0;i<=m;i++){
            dp[i][n]=Integer.MAX_VALUE;
        }
        dp[m][n-1]=1;
        dp[m-1][n]=1;
        for (int i=m-1;i>=0;i--){
            for (int j=n-1;j>=0;j--){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
}
